package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/design-hashmap/">设计哈希映射(Design HashMap)</a>
 * <p>不使用任何内建的哈希表库设计一个哈希映射（HashMap）。</p>
 * <p>实现 MyHashMap 类：
 * <ul>
 *     <li>MyHashMap() 用空映射初始化对象</li>
 *     <li>void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其对应的值 value 。</li>
 *     <li>int get(int key) 返回特定的 key 所映射的 value ；如果映射中不包含 key 的映射，返回 -1 。</li>
 *     <li>void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value 。</li>
 * </ul>
 * </p>
 * <p>
 * <pre>
 * 示例：
 *      输入：
 *          ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
 *          [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
 *      输出：
 *          [null, null, null, 1, -1, null, 1, null, -1]
 *      解释：
 *          MyHashMap myHashMap = new MyHashMap();
 *          myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]]
 *          myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]]
 *          myHashMap.get(1);    // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]]
 *          myHashMap.get(3);    // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
 *          myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
 *          myHashMap.get(2);    // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
 *          myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
 *          myHashMap.get(2);    // 返回 -1（未找到），myHashMap 现在为 [[1,1]]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>0 <= key, value <= 10^6</li>
 * <li>最多调用 10^4 次 put、get 和 remove 方法</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0705DesignHashSet_S 设计哈希集合(Design HashSet)
 * @see LC0706DesignHashMap_S 设计哈希映射(Design HashMap)
 * @see LC707DesignLinkedList_M 设计链表(Design Linked List)
 * @see LC1206DesignSkiplist_H 设计跳表(Design Skiplist)
 * @since 2023/5/10 9:59
 */
public class LC0706DesignHashMap_S {
    static class MyHashMap {
        /*
            由于题目限定了数据范围 0<=key,value<=10^6和 kv 的数据类型。
            可以使用 int 类型的数组实现哈希表功能。
         */
        //private final int[] valArr = new int[1000001];
        //
        //public MyHashMap() {
        //    Arrays.fill(valArr, -1);
        //}
        //
        //public void put(int key, int value) {
        //    valArr[key] = value;
        //}
        //
        //public int get(int key) {
        //    return valArr[key];
        //}
        //
        //public void remove(int key) {
        //    valArr[key] = -1;
        //}

        /*
            数组 + 链表的简单实现
         */

        private static class Node {
            int key;
            int value;
            // 链表解决hash冲突
            Node next;

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        private int getIndex(int key) {
            // 因为 nodes 的长度只有 10009，对应的十进制的 10011100011001（总长度为 32 位，其余高位都是 0）
            // 为了让 key 对应的 hash 高位也参与运算，这里对 hashCode 进行右移异或
            // 使得 hashCode 的高位随机性和低位随机性都能体现在低 16 位中
            return Integer.hashCode(key) % ARR_LENGTH;
        }

        private final int ARR_LENGTH = 10009;

        private final Node[] table = new Node[ARR_LENGTH];

        public MyHashMap() {

        }

        public void put(int key, int value) {
            int idx = getIndex(key);
            Node targetNode = table[idx];
            if (targetNode == null) {
                table[idx] = new Node(key, value);
                return;
            }

            Node tempNode = targetNode;
            Node prevNode = null;
            while (tempNode != null) {
                if (tempNode.key == key) {
                    tempNode.value = value;
                    return;
                }
                prevNode = tempNode;
                tempNode = tempNode.next;
            }
            tempNode = prevNode;
            //// 头插法
            //Node newNode = new Node(key, value);
            //newNode.next = table[idx];
            //table[idx] = newNode;

            // 尾插法
            tempNode.next = new Node(key, value);
        }


        public int get(int key) {
            int idx = getIndex(key);
            Node targetNode = table[idx];
            while (targetNode != null) {
                if (targetNode.key == key) {
                    return targetNode.value;
                }
                targetNode = targetNode.next;
            }
            return -1;
        }

        public void remove(int key) {
            int idx = getIndex(key);
            Node targetNode = table[idx];
            if (targetNode == null) {
                return;
            }
            Node prevNode = null;
            while (targetNode != null) {
                if (targetNode.key == key) {
                    if (prevNode != null) {
                        prevNode.next = targetNode.next;
                    } else {
                        table[idx] = targetNode.next;
                    }
                    return;
                }
                prevNode = targetNode;
                targetNode = targetNode.next;
            }
        }
    }
}